{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Алгоритмы и лямбды"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Откуда ноги растут - из функторов"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Во времена до С++11:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "bool is_underage(const Person& person)\n",
    "{\n",
    "    return person.age < 18;\n",
    "}\n",
    "\n",
    "std::vector<Person> people = { ... };\n",
    "\n",
    "auto it = std::find_if(people.begin(), people.end(), is_underage);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Либо через функтор:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "struct IsUnderageChecker\n",
    "{\n",
    "    bool operator()(const Person& person) const\n",
    "    {\n",
    "        return person.age < 18;\n",
    "    }    \n",
    "};\n",
    "\n",
    "std::vector<Person> people = { ... };\n",
    "        \n",
    "auto it = std::find_if(people.begin(), people.end(), IsUnderageChecker());\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Функтор - класс с определённым `operator()`. Объекты такого класса можно \"вызывать\":\n",
    "\n",
    "**Пример**:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "Person ilya{\"Ilya Muromec\", 32};\n",
    "\n",
    "IsUnderageChecker is_underage_checker;\n",
    "\n",
    "if (is_underage_checker(ilya))\n",
    "    std::cout << \"Ilya is old\";\n",
    "else\n",
    "    std::cout << \"Ilya is young\";\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Конкретно для этого примера (с некоторыми оговорками) не важно, свободная функция `is_underage` или функтор `IsUnderageChecker`, но иногда может понадобится и класс.\n",
    "\n",
    "**Упражение**: Приведите пример. Подсказка: в чём большое отличиие функции от класса?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Вариант**:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "class АgeLessChecker {\n",
    "public:\n",
    "    explicit АgeLessChecker(int bound) : bound_(bound) {}\n",
    "    \n",
    "    bool operator()(const Person& person) const {\n",
    "        return person.age < bound_;\n",
    "    }\n",
    "    \n",
    "private:\n",
    "    int bound_;\n",
    "};\n",
    "\n",
    "\n",
    "Person ilya{\"Ilya Muromec\", 32};\n",
    "\n",
    "АgeLessChecker ilya_maturity_checker{33};\n",
    "\n",
    "if (ilya_maturity_checker(ilya))\n",
    "    std::cout << \"time to fight!\";\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Вариант**:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "class NameInSetChecker {\n",
    "public:\n",
    "    explicit NameInSetChecker(std::set<std::string> allowed_names)\n",
    "        : allowed_names_(std::move(allowed_names))\n",
    "    {}\n",
    "    \n",
    "    bool operator()(const Person& person) const {\n",
    "        return allowed_names_.count(person.name) > 0;\n",
    "    }\n",
    "    \n",
    "private:\n",
    "    std::set<std::string> allowed_names_;\n",
    "};\n",
    "\n",
    "std::vector<Person> people = { ... };\n",
    "\n",
    "const std::set<std::string> allowed_names{\"Balin\", \"Dvalin\", \"Gloin\"};\n",
    "\n",
    "auto it = std::find_if(people.begin(), people.end(),\n",
    "                       NameInSetChecker(allowed_names));\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Более интересный пример**:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "struct HTMLPrinter\n",
    "{\n",
    "    void operator()(int x) const { std::cout << \"<p> int value = \" << x << \" </p>\"; }\n",
    "    void operator()(double x) const { std::cout << \"<p> dlb value = \" << x << \" </p>\"; }\n",
    "};\n",
    "\n",
    "HTMLPrinter printer;\n",
    "printer(5);    // <p> int value = 5 </p>\n",
    "printer(5.0);  // <p> dbl value = 5.000000 </p>\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Правила работы с функторами](https://cpp.com.ru/meyers/ch6.html). Основное:\n",
    "* Классы функторов для алгоритмов передаются по значению, а значит их следует проектировать копируемыми\n",
    "* Желательно, чтобы функторы для алгоритмов не изменяли своё состояние (нет гарантий, что функтор не будет раскопирован))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Функторы - гибкий и богатый инструмент, за исключением того, что требуют большого объёма кода для реализации. Лямбду можно рассматривать как сокращённую запись функтора, который компилятор сгенерирует неявно.*\n",
    "\n",
    "(утверждение может быть поднатянуто с точки зрения оптимизаций, применяемых компилятором к лямбдам и функторам, но для понимания лямбд вполне подойдёт)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Контекст, захват и передача параметров. Dangling references, правила"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Лямбда без состояния:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "auto it = std::find_if(people.begin(), people.end(),\n",
    "                       [](const Person& p){ return p.age < 18; });\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Когда нужно запомнить состояние (сделать поле данных у функтора):"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "auto find_first_younger(const std::vector<Person>& people, int age)\n",
    "{\n",
    "    return std::find_if(people.begin(), people.end(),\n",
    "                        [](const Person& p){ return p.age < age; });    \n",
    "}\n",
    "\n",
    "// Не скомпилируется, т.к. компилятор не знает, каким образом\n",
    "// хранить age в лямбде. Ему нужно это явно указать.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Захватывать данные в лямбду можно двумя способами:\n",
    "1. с копированием значения\n",
    "    * можно представлять как отдельное поле типа `T` в функторе\n",
    "2. по ссылке\n",
    "    * можно представлять  как отдельное поле типа `T*` или `T&` в функторе"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "int age = 33;\n",
    "auto too_young = [age](const Person& p){ return p.age < age; }; \n",
    "age = 18;\n",
    "// age будет скопирован по значению\n",
    "// в поиске используется значение 33\n",
    "\n",
    "std::find_if(people.begin(), people.end(), too_young);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "int age = 33;\n",
    "auto too_young = [&age](const Person& p){ return p.age < age; }; \n",
    "age = 18;\n",
    "// age будет использован по ссылке\n",
    "// в поиске используется значение 18\n",
    "\n",
    "std::find_if(people.begin(), people.end(), too_young);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Можно указывать способ захвата \"по умолчанию\". Тогда все внешние объекты, упоминаемые внутри лямбды, будут захвачены соответственно:\n",
    "\n",
    "* всё захватывать по значению:\n",
    "\n",
    "```c++\n",
    "int age = 33;\n",
    "auto too_young = [=](const Person& p){ return p.age < age; };\n",
    "```\n",
    "\n",
    "* всё захватывать по ссылке:\n",
    "\n",
    "```c++\n",
    "int age = 33;\n",
    "auto too_young = [&](const Person& p){ return p.age < age; };\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Примеры:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "// объект int очень дешёв для копирования,\n",
    "// а разыменовывать по ссылке его дольше,\n",
    "// поэтому захватим по значению\n",
    "\n",
    "int age = read_age_limit();\n",
    "\n",
    "auto it = std::find_if(people.begin(), people.end(),\n",
    "                       [age](const Person& p) { return p.age < age; });\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "// объект std::set<std::string> очень дорогой для копирования,\n",
    "// лучше потратить немножко на дополнительные jump-ы по ссылкам,\n",
    "// поэтому захватим по ссылке\n",
    "\n",
    "std::set<std::string> allowed_names = ...;\n",
    "                \n",
    "auto it = std::find_if(people.begin(), people.end(),\n",
    "                       [&allowed_names](const Person& p) { return allowed_names.count(p.name) > 0; });\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Упражнение:** что здесь происходит?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::set<std::string> allowed_names = ...;\n",
    "std::set<std::string>* p_allowed_names = &allowed_names;\n",
    "                \n",
    "auto it = std::find_if(people.begin(), people.end(),\n",
    "                       [p_allowed_names](const Person& p) { return p_allowed_names->count(p.name) > 0; });\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Dangling references problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "auto make_names_checker()\n",
    "{\n",
    "    std::set<std::string> allowed_names = ...;                \n",
    "    return [&allowed_names](const Person& p) { return allowed_names.count(p.name) > 0; };\n",
    "}\n",
    "\n",
    "auto names_checker = make_names_checker();\n",
    "names_checker(Person(\"Ilya\"));  // ooooops\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* какая здесь проблема?\n",
    "* как с ней бороться?\n",
    "* правила?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Возвращаемый тип"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Компилятор автоматически выводит возвращаемый тип, опираясь на тип выражения в `return`. Но можно и указать тип явно:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "auto too_young = [](const Person& p) { return p.age < 18; };\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "auto too_young = [](const Person& p) -> bool { return p.age < 18; }\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Упражнение**: в каких случаях это необходимо?\n",
    "\n",
    "Ответ-пример:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "// без явного указания типа возвращемого значения код не скопилируется\n",
    "auto build_full_name = [](const Person& p) -> std::string {\n",
    "\n",
    "    // return type is const char *\n",
    "    if (p.name.empty() && p.surname.empty())\n",
    "        return \"unknown\";\n",
    "\n",
    "    // return type is std::string\n",
    "    return p.name + \" \" + p.surname;\n",
    "};\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "// без явного указания типа возвращемого значения код не скопилируется\n",
    "auto find_lowest_point = [](const std::vector<Point>& points) -> std::optional<Point> {\n",
    " \n",
    "    // return type is std::nullopt_t\n",
    "    if (points.empty())\n",
    "        return std::nullopt;\n",
    "    \n",
    "    // return type is Point\n",
    "    return *std::min_element(points.begin(), points.end(),\n",
    "                             [](const Point l, const Point r) { return l.z < r.z; });\n",
    "};\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### mutable - лямбды"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Использование ключевого слова `mutable` означает, что данные, захваченные копированием значения, лямбда вправе поменять:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "void mutable_lambda_example()\n",
    "{\n",
    "    auto fun = [i = 0]() mutable -> bool {\n",
    "        ++i;\n",
    "        return i != 4;\n",
    "    };\n",
    "    while (fun())\n",
    "        std::cout << \"ho\";  // напечатает hohoho\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### immediately call labmdas"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Рассмотрим пример:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "void process_log_file(const std::string& basename)\n",
    "{\n",
    "    const std::string filepath = basename + \".log\";\n",
    "    std::ifstream ifs(filepath);\n",
    "    if (!ifs)\n",
    "        throw std::runtime_error(\"filed to open log file on read\");\n",
    "\n",
    "    std::vector<Record> log_records{std::istreambuf_iterator<Record>(ifs),\n",
    "                                    std::istreambuf_iterator<Record>()};\n",
    "    std::reverse(log_records.begin(), log_records.end());\n",
    "    \n",
    "    \n",
    "    ... 200+ lines of records processing further\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Проблемы такой реализации:\n",
    "* скорее всего `filepath` и `ifs` больше не нужны, но:\n",
    "    - переменные видны в коде ниже и надо разбираться, нужны они там или нет\n",
    "    - переменные держат за собой память и открытый дескриптор файла, а эти ресурсы уже можно и освободить\n",
    "* формирование `log_records` завершено и далее меняться не будет. Его бы как-нибудь пометить `const`, но язык такое не позволяет."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Возможные решения: выделить функцию `read_log_records` или завернуть в immediately call lambda:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "void process_log_file(const std::string& basename)\n",
    "{\n",
    "    const std::vector<Record> log_records = [&basename](){\n",
    "        const std::string filepath = basename + \".log\";\n",
    "        std::ifstream ifs(filepath);\n",
    "        if (!ifs)\n",
    "            throw std::runtime_error(\"filed to open log file on read\");\n",
    "\n",
    "        std::vector<Record> log_records{std::istreambuf_iterator<Record>(ifs),\n",
    "                                        std::istreambuf_iterator<Record>()};\n",
    "        std::reverse(log_records.begin(), log_records.end());\n",
    "        return log_records;\n",
    "    }();\n",
    "    \n",
    "    ... 200+ lines of records processing further\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Не стоит бояться оверхеда в релизе на вызов immediately call - лямбд. Компиляторы хороши в их оптимизации:\n",
    "\n",
    "(закинуть код на godbolt.org)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "// оптимизация для compile-time вычислений\n",
    "int get_5() noexcept {\n",
    "    return [](){ return 5; }();    \n",
    "}\n",
    "\n",
    "// оптимизация для чуть более сложных функций\n",
    "double f_1(const double x, const double y) noexcept {\n",
    "    const double l = x*x +  y*y;\n",
    "    return x / l + y / l;\n",
    "}\n",
    "\n",
    "double f_2(const double x, const double y) noexcept {\n",
    "    const double add1 = [=](){\n",
    "        const double l = x*x + y*y;\n",
    "        return x / l;\n",
    "    }();\n",
    "    const double add2 = [=](){\n",
    "        const double l = x*x + y*y;\n",
    "        return y / l;\n",
    "    }();\n",
    "    return add1 + add2;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Конечно, пример не есть доказательство, но, тем не менее, и gcc, и clang смогли сгенерировать одинаковый код для `f_1` и `f_2`, несмотря на наличие лишних вызовов и доп. вычислений в `f_2`.\n",
    "\n",
    "На уровне оптимизаций для отладки `-O0` компилятор не может себе позволить инлайнить immediately call лямбды, там код отличается, это нормально.\n",
    "\n",
    "Поэтому, если performance для `-O0` важен (бывают такие проекты), то в горячих функциях (коих **очень мало**) лучше воздержаться от immediately call."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### generic lambda"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ничто не мешает сделать `operator()` шаблонным:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "struct HTMLPrinter\n",
    "{\n",
    "    template<typename T>\n",
    "    void operator()(const T& x) const { std::cout << \"<p> value = \" << x << \" </p>\"; }\n",
    "};\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Аналогично можно поступить и для лямбды, заменив тип аргумента словом `auto`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "auto too_young = [](const auto& p) { return p.age < 18; };\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "generic lambda как и template-метод позволяют вызывать для разных аргументов"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "bool f()\n",
    "{\n",
    "    auto less = [](const auto& x, const auto& y) { return x < y; };\n",
    "    return less(3, 5) && less(3.0, 5.0);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Пару слов об использовании и цене"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### `noexcept` lambda"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`noexcept` имеет аналогичную семантику как и `noexcept` для обычных функций."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "auto too_young = [](const auto& p) noexcept { return p.age < 18; };\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Сохранение лямбда-функции как объекта."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Проблема в записи лямбды в поле класса заключается в том, что тип лямбда-функции создаётся в момент генерации лямбды. Его нельзя выписать явно (иногда можно неявно)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Варианты решения проблемы:\n",
    "1. Использовать шаблоны\n",
    "2. Заворачивать лямбды в `std::function`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "class ImagesManager {\n",
    "public:\n",
    "    ImagesManager(std::function<Image(int)> img_searcher)\n",
    "        : img_searcher_(std::move(img_searcher))\n",
    "    {}\n",
    "    \n",
    "    ...    \n",
    "private:\n",
    "    std::function<Image(int, int)> img_searcher_;\n",
    "};\n",
    "\n",
    "// client code:\n",
    "auto search_image = [](const int key) -> Image { ... };\n",
    "ImagesManager manager(search_image);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "template<typename ImgSearcherT>\n",
    "class ImagesManager {\n",
    "public:\n",
    "    ImagesManager() {}\n",
    "    \n",
    "    ...    \n",
    "private:\n",
    "    ImgSearcherT img_searcher_;\n",
    "};\n",
    "\n",
    "\n",
    "// объяснить, почему это вообще работает\n",
    "// client code:\n",
    "auto search_image = [](const int key) -> Image { ... };\n",
    "ImagesManager<decltype(search_image)> manager;\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Упражнение**: каковы плюсы и минусы обоих из вариантов?"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
